const MAZE = [
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0]
];

function aStarSearch(start, end) {
  let openList = [];
  const closeList = [];
  let ret = null;
  //把起点加入 openList
  openList.push(start);
  //主循环，每一轮检查一个当前方格节点
  while (openList.length > 0) {
    // 在openList中查找 F值最小的节点作为当前方格节点
    const currentGridIndex = findMinGirdIndex(openList);
    // 当前方格节点从openList中移除
    const [currentGrid] = openList.splice(currentGridIndex, 1);
    // 当前方格节点进入 closeList
    closeList.push(currentGrid);
    // 找到所有邻近节点
    const neighbors = findNeighbors(currentGrid, openList, closeList);
    neighbors.forEach(grid=>{
      const find = openList.find(item=>item.x === grid.x&&item.y === grid.y);
      if(!find) {
        //邻近节点不在openList中，标记父亲、G、H、F，并放入openList
        grid.initGrid(currentGrid, end);
        openList.push(grid);
      }
    });
    //如果终点在openList中，直接返回终点格子
    openList.forEach(grid => {
      if ((grid.x == end.x) && (grid.y == end.y)) {
        ret = grid;
      }
    })
  }
  //openList用尽，仍然找不到终点，说明终点不可到达，返回空
  return ret;
}

function findMinGirdIndex(openList) {
  let tempGridIndex = 0;
  openList.forEach((grid, i) => {
    if (grid.f < openList[tempGridIndex].f) {
      tempGridIndex = i;
    }
  });
  return tempGridIndex;
}

function findNeighbors(grid, openList, closeList) {
  const gridList = [];
  if (isValidGrid(grid.x, grid.y - 1, openList, closeList)) {
    gridList.push(new Grid(grid.x, grid.y - 1));
  }
  if (isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
    gridList.push(new Grid(grid.x, grid.y + 1));
  }
  if (isValidGrid(grid.x - 1, grid.y, openList, closeList)) {
    gridList.push(new Grid(grid.x - 1, grid.y));
  }
  if (isValidGrid(grid.x + 1, grid.y, openList, closeList)) {
    gridList.push(new Grid(grid.x + 1, grid.y));
  }
  return gridList;
}

function isValidGrid(x, y, openList, closeList) {
  //是否超过边界
  if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
    return false;
  }
  //是否有障碍物
  if (MAZE[x][y] == 1) {
    return false;
  }
  //是否已经在openList中
  if (containGrid(openList, x, y)) {
    return false;
  }
  //是否已经在closeList中
  if (containGrid(closeList, x, y)) {
    return false;
  }
  return true;
}

function containGrid(grids, x, y) {
  let flag = false;
  grids.forEach(grid => {
    if ((grid.x == x) && (grid.y == y)) {
      flag = true;
    }
  });
  return flag;
}

class Grid {
  x;
  y;
  f;
  g;
  h;
  parent;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  initGrid(parent, end) {
    this.parent = parent;
    this.g = parent.g + 1;
    this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
    this.f = this.g + this.h;
  }
}

function run() {
//设置起点和终点
  const startGrid = new Grid(2, 1);
  const endGrid = new Grid(2, 5);
  //搜索迷宫终点
  let resultGrid = aStarSearch(startGrid, endGrid);
  //回溯迷宫路径
  const path = [];
  while (resultGrid != null) {
    path.push(new Grid(resultGrid.x, resultGrid.y));
    resultGrid = resultGrid.parent;
  }
  //输出迷宫和路径，路径用星号表示
  for (let i = 0; i < MAZE.length; i++) {
    let str = '';
    for (let j = 0; j < MAZE[0].length; j++) {
      if (containGrid(path, i, j)) {
        str+='*, '
      } else {
        str+=MAZE[i][j] + ", "
      }
    }
    console.log(str)
  }
}
run();